
//面试题 16.19 水域大小
class Solution {
public:
    vector<int> pondSizes(vector<vector<int>>& land) {
        int n=land.size(),m=land[0].size();
        int dx[]={0,0,1,1,1,-1,-1,-1};  //统计向四周进行扩展的偏移量
        int dy[]={1,-1,0,1,-1,0,1,-1};

        function<int(int,int)> dfs=[&](int x,int y)
        {
            int ret=1;
            land[x][y]=-1;
            for(int k=0;k<8;k++)  //向四周进行扩展
            {
                int a=x+dx[k];
                int b=y+dy[k];
                if(a>=0&&a<n&&b>=0&&b<m&&land[a][b]==0) ret+=dfs(a,b);
            }                
            return ret;
        };
        vector<int> ans;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                if(land[i][j]==0)
                ans.push_back(dfs(i,j));
        }
        sort(ans.begin(),ans.end());
        return ans;
    }
};